<head>
    <meta charset="UTF-8">
<title>算法训练 Binary Key</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p>假设有p和q两个长度为正整数的字符串，我们分别叫它们为匣子和钥匙。</p>
<p>&nbsp;</p>
<p>其中，钥匙串q只包含字符0和1。</p>
<p>&nbsp;</p>
<p>下面给出一段简单的算法用以描述如何从匣子串p中提取出信息串s</p>
<p>i = 0;</p>
<p>j = 0;</p>
<p>s = &lt;&gt;;</p>
<p>while i is less than the length of the string p</p>
<p>{</p>
<p>&nbsp; &nbsp; if q[j] == 1, then add to the right of string s&nbsp;character p[i];</p>
<p>&nbsp; &nbsp; increase variables i, j by one;</p>
<p>&nbsp; &nbsp; if the value of the variable j equals the length&nbsp;of the string q, then j = 0;&nbsp;</p>
<p>}</p>
<p>在上面一段伪代码中 i,j是整形变量，s是字符串， &quot;=&quot;是赋值运算符, &quot;==&quot;是一个比较运算符,&quot;[]&quot;是获取字符串某个下标上的字符的运算符,&quot;&lt;&gt;&quot;是一个空字符串。我们假定所有字符串都是从下标0开始的。</p>
<p>&nbsp;</p>
<p>我们知道这个算法实现起来非常简单，所以你的任务会稍微复杂一些。你需要构造一个字典序最小的长度为k的钥匙串。使该钥匙串用于以上算法时，从给定的匣子串p中获得给定的信息串s</p>
<p>【输入格式】<br />
输入数据的前两行包含两个非空字符串p和s(1 &lt;= |p| &lt;= 10^6, 1 &lt;= |s| &lt;= 200) 分别为上述的匣子串和信息串。这两个字符串可以包含所有ASCII码从32到126的字符。请注意，空格符的ASCII码为32。</p>
<p>输入数据的第三行是一个整数k, (1 &lt;= k &lt;= 2000),钥匙串的长度。<br />
【输出格式】<br />
输出一行包含一个01串，表示你求出来的字典序最小的钥匙串。<br />
【样例输入】<br />
abacaba</p>
<p>aba</p>
<p>6<br />
【样例输出】<br />
100001<br />
【数据规模和约定】</p>
<p>对于25%的数据k &lt;= 20, |p| &lt;= 100</p>
<p>对于50%的数据k &lt;= 60</p>
<p>对于100%的数据k &lt;= 2000, |p| &lt;= 10^6, |s| &lt;= 200</p>
<p>对于两个钥匙串之间的字典序大小的比较方式为比较他们的01字符串的大小</p>